正規言語の特徴付け定理(Myhill-Nerode's theorem)
任意の言語 $ L \subseteq \Sigma^\astに対して、$ R_Lを言語Lによって導入された$ \Sigma^\ast上の同値関係であるとする。このとき、次の3つの命題は互いに同値となる。
ある右不変な同値関係$ Rで、その同値類の個数が有限なものが存在して、$ Lはそのいくつかの同値類の和として表される。
同値関係$ R_Lの同値類の個数は有限である。
マイヒル・ネローデの定理は、ある言語が正規言語ではないことを示すのに便利
証明のアイディア
(1)→(2)
正規言語なのでLを認識するfinite automatonが存在する。
そのfinite automatonにより右不変な同値関係を定義できる
(2)→(3)
$ Rが$ R_Lの細分であることを示す
(3)→(1)
ここが一番面白い
$ R_Lの同値類を状態とみなす
これが右不変であることを示すことで、「状態遷移」がwell-definedであることを示す